#include "link.h"


list* creatlist(void)  //创建表
{
    list* head = (list*)malloc(sizeof(list));
    if (head == NULL)
    {
        printf("%s创建失败!!\n",__func__);
        return NULL;
    }

    head->data=0;
    head->next=NULL;

    return head;
}

datatype InsertHead(list*head , datatype data)//头插法 
{
    //1、分配temp内存
    list* temp = (list*)malloc(sizeof(list));
    if(temp == NULL)
    {
        printf("%s分配失败!!\n",__func__);
        return (datatype) -1;
    }
    //2、传数据
    temp->data = data;
     
    //3、开始插入
    temp->next = head->next;
    head->next = temp;

}

void linkshow(list* head)   //遍历函数
{
    //1、判断是否为空
    if(head->next == NULL)
    {
        printf("链表为空!!\n");
        return ;
    } 
    //2、遍历
      while(head->next!=NULL)
      {
        printf("-%d",head->next->data);
        head = head->next;
      }  
      putchar(10);
}

int  IistIsEmpty(list* head)//判空函数
{
   return head-> next == NULL? 0: -1; 
}

datatype Inserttail(list*head, datatype data )// 尾插法
{
    //1、分配temp内存
    list* temp = (list*)malloc(sizeof(list));
    if(temp == NULL)
    {
        printf("%s分配失败!!\n",__func__);
        return (datatype) -1;
    }
    // 2、使头节点移至最后一个节点
    while(head->next != NULL)
    {
        head = head->next;
    }
    //3、赋值
    temp->data = data; 
    //4、插入
    temp->next = head->next;
    head->next = temp;

    return (datatype)0;
}

datatype listdeletehead(list* head)//头删除
{
    //1、判空
   if(IistIsEmpty(head) == 0)
    {
        printf("IistIsEmpty!!!\n");
        return (datatype)-1;
    }
    //2、保存要删除的数
    list* temp ;
    temp = head->next;
    datatype deletedata = temp->data;
    //3、删除
    head->next = temp->next;
    //4、释放内存
    if(temp != NULL)
    {
        free(temp);
        temp = NULL;
    }
    
    return (datatype) deletedata ;
}

datatype listdeletetail(list* head)//尾删除
{
    //1、判空
   if(IistIsEmpty(head) == 0)
    {
        printf("IistIsEmpty!!!\n");
        return (datatype)-1;
    }
    //2、头节点移至末尾节点前一个位置
    while(head->next->next != NULL)
    {
            head = head->next;
    }
    //3、保存要删除的数
    list* temp ;
    temp = head->next;
    datatype deletedata = temp->data;
    //4、尾删除
    head->next = temp->next;
   //5、释放
   if(temp != NULL)
   {
        free(temp);
        temp = NULL;
   } 
   return deletedata;
}
datatype sinsert(list*head, int data , int pos )//按位置插入
{
    list* temp;
    if(pos<0)
    {
        printf("插入位置不合法!!!\n");
        return (datatype)-1;
    }
    while(head!=NULL)
    {
        if(pos!=0)
        {
            head = head->next;
            pos--;
        }
        else
        {
            temp = (list*)malloc(sizeof(list));
            if(temp==NULL)
            {
                printf("%s为空\n",__func__);
            }
            temp->data = data;

            temp->next = head->next;
            head->next = temp;
             return (datatype) 0;
        }

    }
    printf("插入位置不合法\n");
     return (datatype)-1;
}

datatype sdelete(list*head,  int pos )//按位置删除
{
    list* temp;
    //1、判空
   if(IistIsEmpty(head) == 0)
    {
        printf("IistIsEmpty!!!\n");
        return (datatype)-1;
    }
    if(pos<0)
    {
        printf("删除位置不合法!!!\n");
        return (datatype)-1;
    }
    while(head->next!=NULL)
    {
        if(pos!=0)
        {
            head = head->next;
            pos--;
        }
        else
        {
          
            if(temp==NULL)
            {
                printf("%s为空\n",__func__);
            }
            temp = head->next;
            datatype deletedata = temp->data;

            head->next = temp->next;
            free(temp);
            temp = NULL;
            return deletedata;
        }

    }
    printf("删除位置不合法\n");
     return (datatype)-1;
}


datatype slistshow(list*head,int pos )//按位置查询
{
    //1、判空
   if(IistIsEmpty(head) == 0)
    {
        printf("IistIsEmpty!!!\n");
        return (datatype)-1;
    }
    if(pos<0)
    {
        printf("查询位置不合法!!!\n");
        return (datatype)-1;
    }
    while(head!=NULL)
    {
        if(pos!=0)
        {
            head = head->next;
            pos--;
        }
        else
        {        
        printf("%d\n",head->data); 
        return 0;      
        }
    }
    printf("查询位置不合法\n");
     return (datatype)-1;
}

datatype slistchange(list*head,int pos,int data)//按位置修改
{
    //1、判空
   if(IistIsEmpty(head) == 0)
    {
        printf("IistIsEmpty!!!\n");
        return (datatype)-1;
    }
    if(pos<0)
    {
        printf("修改位置不合法!!!\n");
        return (datatype)-1;
    }
    while(head!=NULL)
    {
        if(pos!=0)
        {
            head = head->next;
            pos--;
        }
        else
        {        
            head->data = data;
            return 0;
        }
    }
    printf("修改位置不合法\n");
     return (datatype)-1;
}

void reverseLinkedList(list* head)
{
   //1、判空
   if(IistIsEmpty(head) == 0)
    {
        printf("IistIsEmpty!!!\n");
        return ;       
    }
    list* s;
    list* l;
    s=head;
    head = head->next;
    s->next = NULL;
    while(head!=NULL)
    {
        l = head;
        head = head->next; 
        l->next = NULL;
        //InsertHead_LinkList(s,l);
        l->next = s->next;
        s->next =l;
    }    
}

void InsertHead_LinkList(list *head,list *tail){
    // if(IistIsEmpty(head) == 0 || IistIsEmpty(tail) == 0){
    //     printf("IistIsEmpty!!!\n");
    //     return ; 
    // }
    // list *save = tail;
    // while(tail->next !=NULL){
    //     tail=tail->next;
    // }
    tail->next = head->next;
    head->next = tail;

}
/*
*功能：实现单向链表的排序
*参数:
@: Head_P : 头节点的地址
*返回值:
 ⽆
*/
void LinkListSort(list *head)
{
 //1、判空
   if(IistIsEmpty(head) == 0)
    {
        printf("IistIsEmpty!!!\n");
        return ;       
    }
 //2、使⽤temp指针指向头节点后⾯的节点
    list *temp;
    temp = head->next;
    head->next = NULL;
 //3、将temp后⾯的所有节点，依次拿出
 //通过⽐较放在合适的节点后⾯
 list *s;//⽤于保存拿出来的节点
 list *SaveHead_P = head;
 while(temp)
 {
    s = temp;
    temp = temp->next;
 //依次取出⼀个节点
 //找到合适的位置 ，插⼊取出的这个节点
 while( (head->next) && (s->data > head->next->data))
 {
    head = head->next;
 }
 //循环结束后，就找到了合适的位置了
 //将s节点放在Head_P链表中
    s->next = head->next;
    head->next = s;
    head = SaveHead_P;
 }
 return ;
}



